package linkedlist;

/**
 * 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。
 * 请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
 * 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，
 * nodes 为节点总数。
 */
public class no328_2 {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null){
            return head;
        }
        ListNode bStart = null;
        ListNode bEnd = null;
        ListNode aStart = null;
        ListNode aEnd = null;
        ListNode cur = head;
        int count = 1;
        while (cur != null){
            if(count % 2 != 0){
                if (bStart == null){
                    bStart = cur;
                    bEnd = cur;
                }else {
                    bEnd.next = cur;
                    bEnd = bEnd.next;
                }
            }else{
                if (aStart == null){
                    aStart = cur;
                    aEnd = cur;
                }else {
                    aEnd.next = cur;
                    aEnd = aEnd.next;
                }
            }
            cur = cur.next;
            count++;
        }
        if(bStart == null){
            return aStart;
        }
        if(aStart == null){
            return bStart;
        }
        aEnd.next = null;
        bEnd.next = aStart;
        return bStart;
    }
}

